﻿// 0819train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <limits>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* BuildNode(vector<int>&tree_vec)
{
    TreeNode* root_node = new TreeNode(tree_vec[0]);
    queue<TreeNode*>bfs_queue;
    bfs_queue.push(root_node);

    int index = 1;
    while (!bfs_queue.empty() && index<tree_vec.size())
    {
        TreeNode* curr_node = bfs_queue.front();
        bfs_queue.pop();

        if (index < tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            curr_node->left = new TreeNode(tree_vec[index]);
        }
        index++;

        if (index < tree_vec.size() && tree_vec[index]!=INT_MIN)
        {
            curr_node->right = new TreeNode(tree_vec[index]);
        }
        index++;
    }

    return root_node;
    //BuildNode
}
/*
 
 */

class Solution01 {
public:
    void inorder(TreeNode* root, vector<int>&res)
    {
        if (!root) return;

        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);

    }

    vector<int> inorderTraversal(TreeNode* root)
	{
        vector<int>res;
        inorder(root, res);
        return res;
    }
};


class Solution02
{
public:
    //map记录中序遍历每个元素的位置，左节点<根节点，右节点>根节点
    map<int, int>inorder_map;
    void insertNode(TreeNode*root, TreeNode*node)
    {
        while (root != node)
        {
            int root_val = root->val;
            int node_val = node->val;

            if (inorder_map[node_val]<inorder_map[root_val])
            {
                if (root->left==nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else if (inorder_map[node_val]>inorder_map[root_val])
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                }
                root = root->right;
            }

        }
	    
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
	{
        //preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
        for (int index=0; index <inorder.size(); index++)
        {
            int curr_num = inorder[index];
            inorder_map[curr_num] = index;
        }

        TreeNode* root = new TreeNode(preorder[0]);
        //遍历前序遍历，插入节点
        for (int i=1; i<preorder.size(); i++)
        {
            insertNode(root, new TreeNode(preorder[i]));

        }
        return root;
        //buildTree------
    }

};


class Solution03
{
public:
    map<int, int>inorder_map;
    void insertNode(TreeNode*root, TreeNode*node)
    {
        if (root == nullptr) return;

        while (root!=node)
        {
            int root_val = root->val;
            int node_val = node->val;
            if (inorder_map[node_val]<inorder_map[root_val])
            {
                if (root->left==nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                }
                root = root->right;
            }

        }

    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        for (int i=0; i<inorder.size(); i++)
        {
            int inorder_num = inorder[i];
            inorder_map[inorder_num] = i;
        }

        int post_size = postorder.size();
        int root_val = postorder[post_size - 1];
        TreeNode* root = new TreeNode(root_val);

        for (int i=post_size-2; i>=0; i--)
        {
            insertNode(root, new TreeNode(postorder[i]));
        }
        return root;
    }


};

/*
 有一棵二叉树，每个节点由一个大写字母标识（最多26个节点），现有两组字母，
 分别表示后序遍历 (左孩子->右孩子->父节点) 和中序遍历 (左孩子->父节点->右孩子) 的结果，
 请输出层次遍历的结果。

输入描述
输入为两个字符串，分别是二叉树的后序遍历和中序遍历结果

输出描述
输出二叉树的层次遍历结果

输入
CBEFDA CBAEDF
输出
ABDCEF

 */

class Solution04
{
public:
    map<char, int>inorder_map;
    queue<TreeNode*>bfs_queue;
    void insertNode(TreeNode*root, TreeNode*node)
    {
        while (root!=node)
        {
            int root_val = root->val;
            int node_val = node->val;
            if (inorder_map[node_val]<inorder_map[root_val])
            {
                if (root->left==nullptr)
                {
                    root->left = node;
                }
                root = root->left;
            }
            else
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                }
                root = root->right;
            }

        }
    }

    void visitTreeNode(TreeNode* root)
    {
        bfs_queue.push(root);

        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();

            vector<int>curr_vec;
            for (int i=0; i<q_size; i++)
            {
                TreeNode* top_node = bfs_queue.front();
                bfs_queue.pop();

                curr_vec.push_back(top_node->val);

                if (top_node->left!=nullptr)
                {
                    bfs_queue.push(top_node->left);
                }
                if (top_node->right!=nullptr)
                {
                    bfs_queue.push(top_node->right);
                }
            }

            string result = "";
            for (auto&oh_char:curr_vec)
            {
                result+=oh_char;
            }
            cout << result;
        }

    }

    vector<char>getCharVec(string&oh_str)
    {
        vector<char>char_vec;
        for (auto&oh_char:oh_str)
        {
            char_vec.push_back(oh_char);
        }
        return char_vec;
    }

    void solve04(string&postorder_str, string&inorder_str)
    {
        vector<char>postorder = getCharVec(postorder_str);
        vector<char>inorder = getCharVec(inorder_str);

        for (int i=0; i<inorder.size(); i++)
        {
            char inorder_val = inorder[i];
            inorder_map[inorder_val] = i;
        }

        int root_val = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(root_val);

        for (int i=postorder.size()-2; i>=0; i--)
        {
            int node_val = postorder[i];
            insertNode(root, new TreeNode(node_val));
        }

        visitTreeNode(root);

    }
	
};

TreeNode* searchBST(TreeNode* root, int val) {
    while (root) {
        if (val == root->val) {
            return root;
        }

        root = val < root->val ? root->left : root->right;
    }
    return nullptr;
}



class Solution05 {
public:
    void insertNode(TreeNode* root, int val)
    {
        while (root->val != val)
        {
            if (val < root->val)
            {
                if (root->left == nullptr)
                {
                    root->left = new TreeNode(val);
                }
                root = root->left;
            }
            else
            {
                if (root->right == nullptr)
                {
                    root->right = new TreeNode(val);
                }
                root = root->right;
            }

        }

    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) return new TreeNode(val);

        insertNode(root, val);
        return root;
    }
};


class Solution06
{
public:
    bool checked(TreeNode*root, long long lower, long long upper)
    {
        if (root == nullptr) return true;

        if (root->val <=lower || root->val>=upper)
        {
            return false;
        }

        return checked(root->left, lower, root->val) && checked(root->right, root->val, upper);
    }

    bool isValidBST(TreeNode* root)
    {
        return checked(root, LONG_MIN, LONG_MAX);
    }


};


int main()
{
	{
        //root = [4,2,7,1,3], val = 5
        vector<int>tree_vec = { 4,2,7,1,3 };
        int val = 5;

        TreeNode* root = BuildNode(tree_vec);
        Solution05 solu;
        solu.insertIntoBST(root, val);

        return 0;
	}
	{
        //root = [4,2,7,1,3], val = 2
        vector<int>tree_vec = { 4,2,7,1,3 };
        int val = 2;

        TreeNode* root = BuildNode(tree_vec);
        searchBST(root, val);

        return 0;
	}
	{
        //vector<char>&postorder, vector<char>&inorder
        //CBEFDA CBAEDF
        string post_str, inorder_str;
        cin >> post_str >> inorder_str;
        //string post_str = "CBEFDA";
        //string inorder_str = "CBAEDF";

        Solution04 solu;
        solu.solve04(post_str, inorder_str);


        return 0;
	}

	{
        //preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
        //vector<int>preorder = { 3,9,20,15,7 };
        //vector<int>inorder = { 9,3,15,20,7 };
        //Solution02 solu;
        //solu.buildTree(preorder, inorder);
        //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
        vector<int>inorder = { 9,3,15,20,7 };
        vector<int>postorder = { 9,15,7,20,3 };
        Solution03 solu;
        solu.buildTree(inorder, postorder);

        return 0;
	}

    const int null = INT_MIN;
    vector<int>tree_vec = { 1,null,2,3 };
    TreeNode* root = BuildNode(tree_vec);
    Solution01 solu;
    solu.inorderTraversal(root);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
